package DataStructure.ArrayLearning.ArrayList;

import java.util.Arrays;

/**
 *  封装数组实现线性表
 * @param <T>
 */
public class MyArrayList <T> {
    // 设置数组最大能容量的长度
    private final int MAX_CAPACITY = (Integer.MAX_VALUE/4) - 8;
    // 声明数组，数组只能用Object类型
    private Object[] arrays;
    // 声明数组已有元素大小
    private int size;

    public MyArrayList() {
        // 创建对象时默认创建长度为10的数组
        arrays = new Object[10];
    }

    public MyArrayList(int initCapacity) {
        // 判断自定义的长度是否异常
        if(initCapacity <= 0 || initCapacity > MAX_CAPACITY) {
            throw new IllegalArgumentException("The parame is Illegal. InitCapacity:" + initCapacity);
        }
        // 调用这个构造方法可以自定义数组初始大小
        arrays = new Object[initCapacity];
    }

    /**
     *  扩容数组
     * @param newLen    新数组长度
     */
    private void grow(int newLen) {
        // 创建新数组
        Object[] newArrays = new Object[newLen];
        // 将旧数组的元素放入新数组里
        for (int i = 0; i < arrays.length; i++) {
            newArrays[i] = arrays[i];
        }
        // 将旧数组的引用换成新数组
        arrays = newArrays;
    }

    /**
     *  获取扩容数组的长度
     * @return  返回新数组长度
     */
    private int getLen() {
        int oldLen = arrays.length;
        // 扩大长度为原来的1.5倍
        // 需要判断长度为1的情况，因为当长度为1时会出现不扩容的情况
        if(oldLen == 1) {
            oldLen = 2;
        }
        int newLen = oldLen + (oldLen >> 1);
        // 判断扩大后的长度是否异常
        if(newLen < 0 || newLen > MAX_CAPACITY) {
            newLen = MAX_CAPACITY;
        }
        if (oldLen == newLen){
            // 数组只能这么大了
            throw  new RuntimeException("arr is max");
        }
        return newLen;
    }

    /**
     *  判断元素内容是否异常以及是否需要扩容数组
     * @param t 新元素
     */
    private void judgeAdd(T t) {
        if (t == null) {
            throw new IllegalArgumentException("The parame is null.");
        }
        expand();
    }

    private void expand() {
        // 当数组满的时候扩容数组
        if (size == arrays.length) {
            int newLen = getLen();
            grow(newLen);
        }
    }

    /**
     *  数组添加功能
     * @param t 新元素
     * @return  返回成功与否
     */
    public boolean add(T t) {
        // 判断新元素是否异常以及是否需要扩容
        judgeAdd(t);
        // 数组有空间可以存放新元素
        arrays[size] = t;
        size++;
        return true;
    }

    /**
     *  添加功能：根据下标添加
     * @param index 下标位置
     * @param t 新元素
     * @return  返回成功与否
     */
    public boolean add(int index, T t) {
        // 判断新元素是否异常以及是否需要扩容
        judgeAdd(t);
        if(index < 0 || index > size) {
            throw new RuntimeException("Out of the memory");
        }
        if(index == size) {
            add(t);
            return true;
        }
        for (int i = size - 1; i >= index; i--) {
            arrays[i+1] = arrays[i];
        }
        arrays[index] = t;
        size++;
        return true;
    }

    /**
     *  移除指定内容匹配的第一个元素
     * @param t 删除的内容
     * @return 返回成功与否
     */
    public boolean remove(T t) {
        // 判断数组里是否有元素
        if(size == 0) {
            return false;
        }
        // 设置坐标
        int tag = 0;
        // 设置寻找标记，当找到元素时标记true
        boolean flag = false;
        // 遍历数组 找到匹配元素
        for (int i = 0; i < arrays.length; i++) {
            if(arrays[i].equals(t)) {
                tag = i;
                flag = true;
                break;
            }
        }
        // 找到匹配元素时进入
        if(flag) {
            // 判断数组空间是否已满
            expand();
            // 将标记位置后面的元素前移覆盖
            for (int i = tag; i < size; i++) {
                arrays[i] = arrays[i+1];
            }
            // 数组长度减一
            size--;
            return true;
        }
        return false;
    }

    /**
     *  删除功能 根据下标删除元素
     * @param index 需要删除的下标
     * @return 返回被删除的元素
     */
    public T remove(int index) {
        // 判断下标值是否异常
        if(index < 0 || index >= size) {
            throw new IllegalArgumentException("Out of the memory");
        }
        // 当数组为空时返回null
        if(size == 0) {
            return null;
        }
        // 接收被删除的元素，需要强制转型
        T oldEle = (T) arrays[index];
        // 判断是否需要扩容数组
        expand();
        // 遍历并将下标值后面的元素前移
        for(int i = index; i<size; i++) {
            arrays[i] = arrays[i+1];
        }
        // 数组长度减一
        size--;
        return oldEle;
    }

    /**
     *  判断功能 判断数组中是否有指定元素
     * @param t 指定元素
     * @return 返回成功与否
     */
    public boolean contains(T t) {
        // 遍历数组，当找到元素时返回true
        for (int i = 0; i < arrays.length; i++) {
            if(arrays[i].equals(t)) {
                return true;
            }
        }
        return false;
    }

    /**
     *
     * @param index
     * @return
     */
    public T get(int index) {
        // 判断下标值是否异常
        if(index < 0 || index >= size) {
            throw new IllegalArgumentException("Out of the memory");
        }
        // 返回下标位置的元素并强转
        return ((T) arrays[index]);
    }

    /**
     *  将匹配到的第一个旧元素替换成新元素
     * @param oldValue  旧元素
     * @param newValue  新元素
     * @return  返回成功与否
     */
    public boolean set(T oldValue, T newValue) {
        // 遍历数组匹配旧元素 找到则替换为新元素
        for (int i = 0; i < arrays.length; i++) {
            if(arrays[i].equals(oldValue)) {
                arrays[i] = newValue;
                return true;
            }
        }
        return false;
    }

    /**
     *  根据下标替换新元素
     * @param index 下标
     * @param newValue 新元素
     * @return 返回被替换的元素
     */
    public T set(int index, T newValue) {
        // 判断下标值是否异常
        if(index < 0 || index >= size) {
            throw new IllegalArgumentException("Out of the memory");
        }
        // 接收旧元素并强转
        T oldValue = ((T) arrays[index]);
        // 将index位置的元素替换为新元素
        arrays[index] = newValue;
        return oldValue;
    }

    @Override
    public String toString() {
        return "{" +
                "arrays=" + Arrays.toString(arrays) +
                ", size=" + size +
                '}';
    }
}
